package com.c2b.algorithm.leetcode.base;

import java.util.*;

/**
 * <a href='https://leetcode.cn/problems/amount-of-time-for-binary-tree-to-be-infected/'>感染二叉树需要的总时间(Amount of Time for Binary Tree to Be Infected)</a>
 * <p>给你一棵二叉树的根节点 root ，二叉树中节点的值 互不相同 。另给你一个整数 start 。在第 0 分钟，感染 将会从值为 start 的节点开始爆发。</p>
 * <p>
 * 每分钟，如果节点满足以下全部条件，就会被感染：
 *     <ul>
 *         <li>节点此前还没有感染。</li>
 *         <li>节点与一个已感染节点相邻。</li>
 *     </ul>
 *     返回感染整棵树需要的分钟数。
 * </p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [1,5,3,null,4,10,6,9,2], start = 3
 *      输出：4
 *      解释：节点按以下过程被感染：
 *          - 第 0 分钟：节点 3
 *          - 第 1 分钟：节点 1、10、6
 *          - 第 2 分钟：节点5
 *          - 第 3 分钟：节点 4
 *          - 第 4 分钟：节点 9 和 2
 *          感染整棵树需要 4 分钟，所以返回 4 。
 *
 * 示例 2：
 *      输入：root = [1], start = 1
 *      输出：0
 *      解释：第 0 分钟，树中唯一一个节点处于感染状态，返回 0 。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>树中节点的数目在范围 [1, 10^5] 内</li>
 *     <li>1 <= Node.val <= 10^5</li>
 *     <li>每个节点的值 互不相同</li>
 *     <li>树中必定存在值为 start 的节点</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/4/25 15:25
 */
public class LC2385AmountOfTimeForBinaryTreeToBeInfected_M {
    static class Solution {

        public int amountOfTime(TreeNode root, int start) {
            Map<Integer, List<Integer>> graph = new HashMap<>();
            dfs(root, graph);
            // 创建队列，用于存储待访问的节点。0:节点值；1：感染到该节点所需时间
            Queue<int[]> queue = new ArrayDeque<>();
            queue.offer(new int[]{start, 0});

            Set<Integer> visited = new HashSet<>();
            visited.add(start);
            // 记录当前时间
            int time = 0;
            while (!queue.isEmpty()) {
                int[] arr = queue.poll();
                time = arr[1];
                // 邻居节点的值
                for (int childVal : graph.get(arr[0])) {
                    if (visited.add(childVal)) {
                        queue.offer(new int[]{childVal, time + 1});
                    }
                }
            }
            return time;
        }

        /**
         * 构建邻接表
         *
         * @param currNode 当前节点
         * @param graph    邻接表
         */
        private void dfs(TreeNode currNode, Map<Integer, List<Integer>> graph) {
            // 如果当前节点存在于邻接表中，则获取其邻居节点列表
            graph.putIfAbsent(currNode.val, new ArrayList<>());
            for (TreeNode child : Arrays.asList(currNode.left, currNode.right)) {
                if (child != null) {
                    // 如果子节点存在，则将其加入当前节点的邻居节点列表中
                    graph.get(currNode.val).add(child.val);
                    // 如果子节点不存在于邻接表中，则为其创建邻居节点列表。并将当前节点添加到子节点的邻接表中
                    graph.putIfAbsent(child.val, new ArrayList<>());
                    graph.get(child.val).add(currNode.val);
                    dfs(child, graph);
                }
            }
        }
    }

    public static void main(String[] args) {
        //TreeNode root = new TreeNode(1);
        //root.left = new TreeNode(5);
        //root.right = new TreeNode(3);
        //root.right.left = new TreeNode(10);
        //root.right.right = new TreeNode(6);
        //root.left.right = new TreeNode(4);
        //root.left.right.left = new TreeNode(9);
        //root.left.right.right = new TreeNode(2);
        //
        //Solution solution = new Solution();
        //System.out.println(solution.amountOfTime(root, 3));
        //
        //System.out.println(solution.amountOfTime(new TreeNode(1), 1));

        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.left.left = new TreeNode(4);
        root.left.left.left.left = new TreeNode(5);
        Solution solution = new Solution();
        System.out.println(solution.amountOfTime(root, 1));
    }
}
